# 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
# n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
# 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
# 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
#
#  示例 1：
# 输入：n = 4
# 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
# 解释：如上图所示，4 皇后问题存在两个不同的解法。
#
#  示例 2：
# 输入：n = 1
# 输出：[["Q"]]
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # res[i] 为一个list[int] 代表一个单独的结果集tmp_res
        # tmp_res[j] = m 代表当前结果的 i 行 j 列 放的是皇后
        res, single_res = list[list[int]](), list[int]()
        used = [False] * n
        # used_plus 主对角线， used_minus 副对角线
        used_plus, used_minus = {}, {}

        def dfs(row: int) -> None:
            if row == n:
                res.append(single_res[:])
                return
            for col in range(n):
                if not used[col] and not used_plus.get(row + col, False) and not used_minus.get(row - col, False):
                    single_res.append(col)
                    used[col] = True
                    used_plus[row + col] = True
                    used_minus[row - col] = True
                    dfs(row + 1)
                    used_minus[row - col] = False
                    used_plus[row + col] = False
                    used[col] = False
                    del single_res[-1]

        dfs(0)
        # result = []
        # for p in res:
        #     pattern = [['.' for _ in range(n)] for _ in range(n)]
        #     for row in p:
        #         pattern[row][p[row]] = 'Q'
        #     result.append([''.join(p) for p in pattern])

        # print(res)
        # print(result)

        def covert_to_res(tmp_res: list[int]) -> list[str]:
            pattern = [['.' for _ in range(n)] for _ in range(n)]
            for r in tmp_res:
                pattern[r][tmp_res[r]] = 'Q'
            return [''.join(p) for p in pattern]
        return [covert_to_res(t) for t in res]


if __name__ == "__main__":
    print(Solution().solveNQueens(4))
